Computing devices are often used to communicate over a network such as the Internet. Network-based services offered by a service provider are becoming more commonplace. Computing devices are frequently used to connect to a network based service, which can provide services such as storing searchable data or providing additional processing power to the computing devices. An increasing number of customers of such a service utilize resources of the service to enable users to search customer-provided data. As the amount of customer data increases and the queries become more complex, the time it takes to execute these queries can increase as well. While additional resources can be used to attempt to reduce the latency, these resources come at an additional cost and the addition of several resources may be too expensive for a customer. This provides difficulty for customers who have specific requirements for the queries of their users, such as a maximum latency.